/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */ //解法1::
class Solution {
public:
    class an{
        public:
        int type; //0表示找到了p 1表示找到q 2表示都找到了 -1表示啥都没找到
        TreeNode* root; 

        an(int type,TreeNode* root):type(type),root(root){}
        an(int type):type(type),root(nullptr){}
    };
    an dfs(TreeNode* root,TreeNode* p,TreeNode*q){
        if(!root){
            return an(-1); //若空返回-1
        }

        an ret1=dfs(root->left,p,q); //先看左子树能否找到

        if(ret1.type==-1){ //若左子树什么都没找到
            an ret2=dfs(root->right,p,q); //找右子树

            if(root==p){ //若当前节点是p或者q结合ret2判断该返回什么类型
                if(ret2.type==0||ret2.type==1){
                    return an(2,root);
                }
                return an(0,root);
            }
            if(root==q){
                if(ret2.type==0||ret2.type==1){
                    return an(2,root);
                }
                return an(1,root);
            }

            return ret2; //若都不是 返回ret2
        }else if(ret1.type==0||ret1.type==1){ //若是0或1
            if(root==p||root==q){ //若当前节点即p或q直接返回2
                return an(2,root);
            }

            an ret2=dfs(root->right,p,q); //若不是找右子树

            if(ret2.type==0||ret2.type==1){
                return an(2,root);
            }

            return ret1;
        }else{
            return ret1;
        }
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return dfs(root,p,q).root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */ //解法2:
class Solution {
public:
    TreeNode* dfs(TreeNode* root,TreeNode* p,TreeNode*q){
        if(!root||root==p||root==q) return root; //若当前节点即要找的节点直接返回

        TreeNode* left=dfs(root->left,p,q); //找左子树
        TreeNode* right=dfs(root->right,p,q); //找右子树

        if(!left) return right; //若左子树没找到直接返回右
        if(!right) return left;

        return root; //若左右都能找到说明当前节点是最近祖先节点
    } 

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return dfs(root,p,q);
    }
};